// Copyright (C) 2012 Yury Bychenkov (http://bychenkov.com).
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
//  - Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
//  - Redistributions in binary form must reproduce the above
// copyright notice, this list of conditions and the following disclaimer
// in the documentation and/or other materials provided with the
// distribution.
//  - Neither the name of Yury Bychenkov nor the names of its
// contributors may be used to endorse or promote products derived from
// this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

template <typename Key, typename Value>
HashMap<Key, Value>::Entry::Entry(const Key& key_, const Value& value_):
	key(key_),
	value(value_)
{
}

template <typename Key, typename Value>
typename HashMap<Key, Value>::Page* HashMap<Key, Value>::getPage(uint pageIndex) const {
	return (Page*) (pages + (pageIndex - 1) * pageSize);
}

template <typename Key, typename Value>
uint HashMap<Key, Value>::estimateCapacity(size_t poolSize, uint blockSize) {
   	uint capacity = (uint) (poolSize * 8 / (blockSize * 8 + 1));
	while (((capacity + sizeof(uint8) - 1) / sizeof(uint8) + blockSize - 1) / blockSize + capacity > poolSize / blockSize) {
		capacity--;
	}
	return capacity;
}

template <typename Key, typename Value>
HashMap<Key, Value>::HashMap(uint8* pool, size_t poolSize, uint pageSize_, uint bucketCount_):
	buckets((uint32*) pool),
	bucketCount(bucketCount_),
	bitmap((uint8*) (buckets + bucketCount)),
	pageSize(pageSize_),
	pageCount(estimateCapacity(poolSize - bucketCount * sizeof(uint32), pageSize)),
	pageCapacity((pageSize - 2 * sizeof(uint32)) / (sizeof(Entry))),
	pages(bitmap + (pageCount + 7) / 8)
{
	memset(buckets, 0, bucketCount * sizeof(uint32));
	memset(bitmap, 0, (pageCount + 7) / 8);
}

template <typename Key, typename Value>
typename HashMap<Key, Value>::Entry* HashMap<Key, Value>::get(const Key& key) const {
	uint pageIndex = buckets[hash(key)];

	while (pageIndex != 0) {
		Page* page = getPage(pageIndex);
		
		pageIndex = page->next;
	
	    Entry* entry = page->entries;
		for (int i = page->count; i > 0; i--, entry++) {
			if (entry->key == key) {
				return entry;
			}
		}
	}

	return 0;
}

template <typename Key, typename Value>
typename HashMap<Key, Value>::Entry* HashMap<Key, Value>::put(const Key& key, const Value& value) {
	return put(key, value, false);
}

template <typename Key, typename Value>
typename HashMap<Key, Value>::Entry* HashMap<Key, Value>::putIfAbsent(const Key& key, const Value& value) {
	return put(key, value, true);
}

template <typename Key, typename Value>
typename HashMap<Key, Value>::Entry* HashMap<Key, Value>::put(const Key& key, const Value& value, bool ifAbsent) {

	const uint bucketIndex = hash(key);
	uint pageIndex = buckets[bucketIndex];

	uint underflowPageIndex = 0;

	while (pageIndex != 0) {
		Page* page = getPage(pageIndex);
		
		uint nextPageIndex = page->next;

	    Entry* entry = page->entries;

		for (int i = page->count; i > 0; i--, entry++) {
			if (entry->key == key) {
				if (!ifAbsent) {
					entry->value = value;
				}
				return entry;
			}
		}

		if (underflowPageIndex == 0 && pageCapacity > page->count) {
			underflowPageIndex = pageIndex;
		}

		pageIndex = nextPageIndex;
	}


	if (underflowPageIndex == 0) {
		uint8 mask = bitmap[0];
		pageIndex = 0;
		while (pageIndex < pageCount && mask == 0xFF) {
			pageIndex += 8;
			mask = bitmap[pageIndex >> 3];
		}

		while (pageIndex < pageCount && (mask & 1) != 0) {
			pageIndex++;
			mask >>= 1;
		}

		if (pageIndex >= pageCount) {
			return 0;
		}
		bitmap[pageIndex >> 3] |= 1 << (pageIndex & 7);

		pageIndex++;
		
		Page* page = getPage(pageIndex);

		page->next = buckets[bucketIndex];
		page->count = 0;
		buckets[bucketIndex] = pageIndex;
	} else {
		pageIndex = underflowPageIndex;
	}

	Page* page = getPage(pageIndex);
	Entry* entry = &page->entries[page->count++];
	
	new (entry) Entry(key, value);

	return entry;
}

template <typename Key, typename Value>
uint HashMap<Key, Value>::hash(const Key& key) const {
	return uint(key) % bucketCount;
}

template <typename Key, typename Value>
bool HashMap<Key, Value>::remove(const Key& key, Value* valueOut) {
	const uint bucketIndex = hash(key);

	const uint firstPageIndex = buckets[bucketIndex];
	
	uint pageIndex = firstPageIndex;

	while (pageIndex != 0) {
		Page* page = getPage(pageIndex);
		
		Entry* entry = page->entries;
		for (int i = page->count; i > 0; i--, entry++) {
			if (entry->key == key) {
				if (valueOut != 0) {
					*valueOut = entry->value;
				}

				Page* firstPage = getPage(firstPageIndex);
				firstPage->count--;
				*entry = firstPage->entries[firstPage->count];
				if (firstPage->count == 0) {
					buckets[bucketIndex] = firstPage->next;
					bitmap[firstPageIndex >> 3] &= ~(1 << (firstPageIndex & 7));
				}
				
				return true;
			}
		}

		pageIndex = page->next;
	}

	return false;	
}

template <typename Key, typename Value>
typename HashMap<Key, Value>::Iterator HashMap<Key, Value>::iterator() const {
	return Iterator(*this);
}

template <typename Key, typename Value>
HashMap<Key, Value>::Iterator::Iterator(const HashMap& map_):
	map(map_)
{
	bucketIndex = 0;
	while (bucketIndex < map.bucketCount && map.buckets[bucketIndex] == 0) {
		bucketIndex++;
	}
	if (bucketIndex < map.bucketCount) {
		page = map.getPage(map.buckets[bucketIndex]);
		entryIndex = 0;
	}
}

template <typename Key, typename Value>
bool HashMap<Key, Value>::Iterator::hasNext() const {
	return bucketIndex < map.bucketCount;
}

template <typename Key, typename Value>
const typename HashMap<Key, Value>::Entry* HashMap<Key, Value>::Iterator::next() {
	if (bucketIndex >= map.bucketCount) {
		return 0;
	}

	const Entry* result = &page->entries[entryIndex++];
	if (entryIndex >= page->count) {
		if (page->next != 0) {
			page = map.getPage(page->next);
			entryIndex = 0;
		} else {
			bucketIndex++;
			while (bucketIndex < map.bucketCount && map.buckets[bucketIndex] == 0) {
				bucketIndex++;
			}
			if (bucketIndex < map.bucketCount) {
				page = map.getPage(map.buckets[bucketIndex]);
				entryIndex = 0;
			}
		}
	}

	return result;
}
